package com.gao.alg.geek;

import java.util.HashMap;
import java.util.Map;

/**
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 */
public class ClimbStairs {

    Map<Integer,Integer> map = new HashMap<>();
    /**
     * 费波纳茨数列
     * f(n) = f(n-1) + f(n-2)
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n <= 2){
            return n;
        }
        int count = climbStairs(n-1) + climbStairs(n-2);
        return count;
    }

    /**
     * 缓存可以极大提高效率
     *
     * @param n
     * @return
     */
    public int climbStairsWithCache(int n) {
        if (n <= 2){
            return n;
        }
        if (map.containsKey(n)){
            return map.get(n);
        }
        int count = climbStairsWithCache(n-1) + climbStairsWithCache(n-2);
        map.put(n,count);
        return count;
    }

    /**
     * 递归转迭代循环
     * 1 2 3 5 8
     */
    public int climbStairs2Array(int n) {
        if (n==1){
            return 1;
        }
        if (n==2){
            return 2;
        }
        int ret = 0;
        int pre =2;
        int prepare = 1;
        for (int i = 3; i <= n; i++) {
            ret = pre + prepare;
            prepare = pre;
            pre = ret;
        }
        return ret;
    }

}
